#include "Ej1.h"
#include <iostream>     // std::cout, std::cin
#include <algorithm>
#include <vector>
#include <tuple> 
#include <set>
#include <string>
#include <queue>   
#include <map>
#include <forward_list>

using namespace std;

map < string, map < string, vector< pair<unsigned int, unsigned int> > > > ciudades;
map < string, tuple < string, int, int> > visitados;
string stringViajes;
string origen;
string destino;

Ej1::Ej1()
{

}


Ej1::~Ej1()
{
}

struct Comparador{
	bool operator()(tuple<string, unsigned int, string> i, tuple<string, unsigned int, string> j)
	{
		return (get<1>(i) > get<1>(j));
	}
};

void Ej1::Procesar(){
	// (ciudad origen, hora llegada, ciudad destino)
	forward_list<  tuple<string, unsigned int, string> > cola;	
	tuple<string, unsigned int, string> a = make_tuple(origen, 0, origen);	
	visitados.clear();
	for (map < string, map < string, vector< pair<unsigned int, unsigned int> > > >::iterator it = ciudades.begin(); 
		it != ciudades.end(); 
		++it) {
		visitados.insert(make_pair(it->first, make_tuple("-1", -1, -1))); 
	}
	visitados[origen] = make_tuple("", 0, 0);
	map<string,int> recorridos;	
	set<string>::iterator it;	

	forward_list< tuple<string, unsigned int, string> >::iterator rm,min,colaIt,colaItPrev;	

	bool seguir = true;
	while (seguir)
	{
		
		string ciudadid = get<2>(a);
		//cout << "actual "<< ciudadid << "\n";
		recorridos[ciudadid] = 1;
		unsigned int horallegada = get<1>(a);
		//unsigned int origen = get<0>(a);

		//printf("entro al if\n");
		for (map < string, map < string, vector< pair<unsigned int, unsigned int> > > >::iterator ciudadesIt = ciudades.begin(); ciudadesIt != ciudades.end(); ++ciudadesIt)
		{
			string i = ciudadesIt->first;
			if (i == ciudadid)
				continue;

			for (unsigned int v = 0; v < ciudades[ciudadid][i].size(); v++)
			{
				unsigned int sale = get<0>(ciudades[ciudadid][i][v]);
				unsigned int llega = get<1>(ciudades[ciudadid][i][v]);
				
				if ( ciudadid == origen || ((unsigned int)(horallegada+2) <= sale))  
				{
					//cout << "comparacion "<< horallegada << " sale " << sale <<	"\n";
					//puedo tomar ese vuelo
					if ((get<0>(visitados[i]) == "-1") && (get<1>(visitados[i]) == -1) && 
						(get<2>(visitados[i]) == -1))
					{
						visitados[i] = make_tuple(ciudadid, sale, llega);
						cola.push_front(make_tuple(ciudadid, llega, i));
						//cout << "actualize arriba \n";
					}
					if (  llega < (unsigned int)get<2>(visitados[i]))
					{
						visitados[i] = make_tuple(ciudadid, sale, llega);
						cola.push_front(make_tuple(ciudadid, llega, i));
						//cout << "actualize abajo \n";
						//cout << " vuelo de " << ciudadid << " a " << i << ", sale a las " << sale << " llega a las " << llega << "\n";
					}
				}else{
					//cout << "comparacion no "<< horallegada << " sale " << sale << "\n";
				}
			}

		}
		
		if (!cola.empty())
		{
			colaIt =  cola.begin();
			
			int t = 0;
			do{
				//remuevo los vuelos que van a ciudades que  ya recorridos
				if ( recorridos[ get<2>(*colaIt) ] == 1){
					if (t ==0 ){
						//cout << "erase 0 (" << get<0>(*colaIt) << ", " << get<1>(*colaIt) << ", " << get<2>(*colaIt) << ") ====\n";
						cola.pop_front();
						colaIt = cola.begin();
					}else{
						//cout << "erase 1 (" << get<0>(*colaIt) << ", " << get<1>(*colaIt) << ", " << get<2>(*colaIt) << ") ====\n";
						//cout << "erase 1  prev(" << get<0>(*colaItPrev) << ", " << get<1>(*colaItPrev) << ", " << get<2>(*colaItPrev) << ") ====\n";
						cola.erase_after(colaItPrev);
						colaIt = colaItPrev;
						colaIt ++;
					}
				}else{
					//cout << "erase 2 (" << get<0>(*colaIt) << ", " << get<1>(*colaIt) << ", " << get<2>(*colaIt) << ") ====\n";
					if (t == 0 ||  get<1>(*min)> get<1>(*colaIt) ){
						min = colaIt;
						//cout << "(" << get<0>(*min) << ", " << get<1>(*min) << ", " << get<2>(*min) << ") ====\n";	
					}
					colaItPrev = colaIt;
					colaIt++;
					t++;
				}
				

			}while( !cola.empty()  && colaIt != cola.end() );
			if (!cola.empty()){
				a = *min;
				//cout << "(" << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << ") |||||\n";
			}else{
				seguir = false;
			}
		}
		else
		{
			seguir = false;
		}
		//cout << "loop -------------- \n";
	}

	// for (map< string, tuple< string, int, int> > ::iterator it = visitados.begin(); it != visitados.end(); ++it)
	// {
	// 	cout << "("<< it->first<< "|||" << get<0>(it->second) << ", " << get<1>(it->second) << ", " << get<2>(it->second) << ") ";
	// }
}

void Ej1::Procesar_Entrada(string entrada)
{
	//cout << "Entrada: " << entrada << "\n";

	ciudades.clear();
	
	int sep = entrada.find(" ");
	origen = entrada.substr(0, entrada.find(" "));
	entrada.erase(0,sep+1);
	sep = entrada.find(" ");
	destino = entrada.substr(0,sep);

	entrada.erase(0,sep+1);
	sep = entrada.find(" ");
	
	string vuelosCStr = entrada.substr(0,sep);
	//int vuelosC = stoi(vuelosCStr);

	//cout << "|" << origen << "|" <<destino<< "|"<< vuelosC << "\n";
	
	entrada.erase(0, sep+1);
	//primero busco todas las ciudades
	int pos = 0;
	string stringCiudades = entrada;
	stringViajes = entrada;
	vector<string> ciudadesSplit;
	vector<string>::iterator buscadorIt;

	while (stringCiudades.size() > 1) {
		pos = stringCiudades.find(" ");
		string ciudad = stringCiudades.substr(0, pos);
		buscadorIt = find(ciudadesSplit.begin(), ciudadesSplit.end(), ciudad);

		if (buscadorIt == ciudadesSplit.end())
		{
	//		cout << " pusheo ciudad 1 " << ciudad << "\n"; 
			ciudadesSplit.push_back(ciudad);
		}

		stringCiudades.erase(0, pos + 1);

		pos = stringCiudades.find(" ");
		ciudad = stringCiudades.substr(0, pos);

		buscadorIt = find(ciudadesSplit.begin(), ciudadesSplit.end(), ciudad);

		if (buscadorIt == ciudadesSplit.end())
		{
	//		cout << " pusheo ciudad 2 " << ciudad << "\n"; 
			ciudadesSplit.push_back(ciudad);
		}
		stringCiudades.erase(0, pos + 1);

		pos = stringCiudades.find(" ");
		stringCiudades.erase(0, pos + 1);

		pos = stringCiudades.find(" ");
		stringCiudades.erase(0, pos + 1);
	//	cout << "entro \n" ;
	}
	
	for (vector<string>::iterator matrizIt = ciudadesSplit.begin(); ciudadesSplit.end() != matrizIt; ++matrizIt)
	{
		map < string, vector<pair<unsigned int, unsigned int> > > ciudad;
		for (vector<string>::iterator matrizIt2 = ciudadesSplit.begin(); ciudadesSplit.end() != matrizIt2; ++matrizIt2)
		{
			vector<pair<unsigned int, unsigned int> > viajesVacios;
			ciudad.insert(make_pair(*matrizIt2, viajesVacios));
		}

		ciudades.insert(make_pair(*matrizIt, ciudad));
	}

	while (entrada.size() > 1)
	{
		pos = entrada.find(" ");
		string origen = entrada.substr(0, pos);
		entrada.erase(0, pos + 1);

		pos = entrada.find(" ");
		string destino = entrada.substr(0, pos);
		entrada.erase(0, pos + 1);

		pos = entrada.find(" ");
		unsigned int sale = stoi(entrada.substr(0, pos));
		entrada.erase(0, pos + 1);

		pos = entrada.find(" ");
		unsigned int llega = stoi(entrada.substr(0, pos));
		entrada.erase(0, pos + 1);
		//cout << "origen " << origen << " destino "<< destino <<"sale "<< sale << " llega "<< llega <<"\n";
		ciudades[origen][destino].push_back(make_pair(sale, llega));
	}
}

void Ej1::Imprimir_Salida(){

	vector< tuple<string, string, unsigned int, unsigned int> > recorrido;
	string origenV = get<0>(visitados[destino]);
	string destinoV = destino;
	unsigned int sale = get<1>(visitados[destino]);
	unsigned int llega = get<2>(visitados[destino]);

	recorrido.push_back(make_tuple(origenV, destinoV, sale, llega));
	while ((origenV != "-1" && origenV != origen))
	{
		destinoV = origenV;
		origenV = get<0>(visitados[destinoV]);
		sale = get<1>(visitados[destinoV]);
		llega = get<2>(visitados[destinoV]);
		recorrido.push_back(make_tuple(origenV, destinoV, sale, llega));
	}

	if (origenV == "-1")
	{
		cout << "no";
	}
	else
	{
		reverse(recorrido.begin(), recorrido.end());
		string viajesSalida = "";
		for (vector< tuple<string, string, unsigned int, unsigned int> >::iterator it = recorrido.begin(); it != recorrido.end(); ++it)
		{
			string viajesOriginal = stringViajes;
			int contador = 1;
			int pos = 0;

			while (viajesOriginal.size() > 1)
			{
				pos = viajesOriginal.find(" ");
				string origen = viajesOriginal.substr(0, pos);
				viajesOriginal.erase(0, pos + 1);

				pos = viajesOriginal.find(" ");
				string destino = viajesOriginal.substr(0, pos);
				viajesOriginal.erase(0, pos + 1);

				pos = viajesOriginal.find(" ");
				unsigned int sale = stoi(viajesOriginal.substr(0, pos));
				viajesOriginal.erase(0, pos + 1);

				pos = viajesOriginal.find(" ");
				unsigned int llega = stoi(viajesOriginal.substr(0, pos));
				viajesOriginal.erase(0, pos + 1);

				tuple<string, string, unsigned int, unsigned int> temp = make_tuple(origen, destino, sale, llega);

				if (temp == *it)
				{
					break;
				}

				contador++;
			}

			viajesSalida = viajesSalida + to_string(contador) + " ";
		}

		cout << get<2>(visitados[destino]) << " " << recorrido.size() << " " << viajesSalida << "\n";
	}
}

void Ej1::Ejecutar(string entrada)
{
	Procesar_Entrada(entrada);
	Procesar();
	Imprimir_Salida();
}

